package com.heima.leetcode.practice;

import java.util.HashSet;
import java.util.List;

/**
 * @description: leetcode 139. 单词拆分
 * @author 勾新杰
 * @version 1.0
 * @date 2025/1/16 9:50
 */
public class E139 {

    /**
     * 存放单词
     */
    private final HashSet<String> set = new HashSet<>();

    /**
     * <h3>方法一：动态规划</h3>
     * @param s 字符串
     * @param wordDict 单词列表
     * @return 是否可以拆分
     */
    public boolean wordBreak1(String s, List<String> wordDict) {
        // 1. 将单词列表添加到HashSet中，提高查找效率
        set.addAll(wordDict);
        // 2. 创建一个长度为s.length() + 1的布尔数组，用于记录前0-i是否可以拆分。
        int length = s.length();
        boolean[] dp = new boolean[length + 1];
        // 3. 初始化dp[0]为true，表示空字符串可以拆分。
        dp[0] = true;
        // 4. 遍历字符串s，计算dp[i]的值。
        for (int i = 1; i <= length; i++){
            for (int j = 0; j <= i - 1; j++){
                // 如果前1 - j部分可以拆分，并且后j+1 - i部分是单词，则前1 - i部分可以拆分。
                if (dp[j] && set.contains(s.substring(j, i))){
                    dp[i] = true;
                    break;
                }
            }
        }
        // 5. 返回dp[length]的值，表示整个字符串是否可以拆分。
        return dp[length];
    }

    /**
     * 记录单词列表
     */
    private List<String> wordDict;

    /**
     * 记录当前偏移量对应的位置是否已经尝试过，避免重复尝试。
     */
    private boolean[] bad;

    /**
     * <h3>方法二：回溯加记忆法</h3>
     * @param s 字符串
     * @param wordDict 单词列表
     * @return 是否可以拆分
     */
    public boolean wordBreak2(String s, List<String> wordDict) {
        this.wordDict = wordDict;
        this.bad = new boolean[s.length()];
        return wordBreakHelper(s, 0);
    }

    /**
     * 回溯算法
     * @param s 字符串
     * @param offset 偏移量
     * @return 是否可以拆分
     */
    private boolean wordBreakHelper(String s, int offset) {
        // 递归结束条件：递归到字符串末尾，说明可以拆分
        if (s.length() == offset) return true;
        // 递归结束条件：当前偏移量对应的位置已经标记为不可拆分，说明之前已经尝试过，直接返回false
        if (bad[offset]) return false;
        // 遍历单词列表，尝试将当前偏移量开始的子串拆分成单词，如果可以拆分，则递归调用wordBreakHelper函数继续尝试下一个位置。
        for (String word : wordDict)
            if (s.startsWith(word, offset))
                if (wordBreakHelper(s, offset + word.length()))
                    return true;
        // 如果无法拆分，则将当前偏移量对应的位置标记为不可拆分，并返回false。
        bad[offset] = true;
        return false;
    }
}
